{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!--BOOK_INFORMATION-->\n",
    "<a href=\"https://www.packtpub.com/big-data-and-business-intelligence/machine-learning-opencv\" target=\"_blank\"><img align=\"left\" src=\"data/cover.jpg\" style=\"width: 76px; height: 100px; background: white; padding: 1px; border: 1px solid black; margin-right:10px;\"></a>\n",
    "*This notebook contains an excerpt from the book [Machine Learning for OpenCV](https://www.packtpub.com/big-data-and-business-intelligence/machine-learning-opencv) by Michael Beyeler.\n",
    "The code is released under the [MIT license](https://opensource.org/licenses/MIT),\n",
    "and is available on [GitHub](https://github.com/mbeyeler/opencv-machine-learning).*\n",
    "\n",
    "*Note that this excerpt contains only the raw code - the book is rich with additional explanations and illustrations.\n",
    "If you find this content useful, please consider supporting the work by\n",
    "[buying the book](https://www.packtpub.com/big-data-and-business-intelligence/machine-learning-opencv)!*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!--NAVIGATION-->\n",
    "< [Understanding Cross-Validation](11.02-Understanding-Cross-Validation-Bootstrapping-and-McNemar's-Test.ipynb) | [Contents](../README.md) | [Chaining Algorithms Together to Form a Pipeline](11.04-Chaining-Algorithms-Together-to-Form-a-Pipeline.ipynb) >"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Tuning Hyperparameters with Grid Search\n",
    "\n",
    "The most commonly used tool for hyperparameter tuning is **grid search**, which is basically\n",
    "a fancy term for saying we will try all possible parameter combinations with a for loop.\n",
    "\n",
    "Let's have a look at how that is done in practice."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Implementing a simple grid search\n",
    "\n",
    "Returning to our $k$-NN classifier, we find that we have only one hyperparameter to tune: $k$.\n",
    "Typically, you would have a much larger number of open parameters to mess with, but the\n",
    "$k$-NN algorithm is simple enough for us to manually implement grid search.\n",
    "\n",
    "Before we get started, we need to split the dataset as we have done before into training and\n",
    "test sets. Here we choose a 75-25 split:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "from sklearn.datasets import load_iris\n",
    "import numpy as np\n",
    "iris = load_iris()\n",
    "X = iris.data.astype(np.float32)\n",
    "y = iris.target"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from sklearn.model_selection import train_test_split\n",
    "X_train, X_test, y_train, y_test = train_test_split(\n",
    "    X, y, random_state=37\n",
    ")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Then the goal is to loop over all possible values of $k$. As we do this, we want to keep track of\n",
    "the best accuracy we observed as well as the value for $k$ that gave rise to this result:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "best_acc = 0\n",
    "best_k = 0"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Grid search then looks like an outer loop around the entire train and test procedure. After calculating the accuracy on the test set (`acc`), we compare it to the best accuracy found\n",
    "so far (`best_acc`). If the new value is better, we update our bookkeeping variables and\n",
    "move on to the next iteration:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "import cv2\n",
    "from sklearn.metrics import accuracy_score\n",
    "for k in range(1, 20):\n",
    "    knn = cv2.ml.KNearest_create()\n",
    "    knn.setDefaultK(k)\n",
    "    knn.train(X_train, cv2.ml.ROW_SAMPLE, y_train)\n",
    "    _, y_test_hat = knn.predict(X_test)\n",
    "    acc = accuracy_score(y_test, y_test_hat)\n",
    "    if acc > best_acc:\n",
    "        best_acc = acc\n",
    "        best_k = k"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "When we are done, we can have a look at the best accuracy:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(0.97368421052631582, 1)"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "best_acc, best_k"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Turns out, we can get 97.4% accuracy using $k=1$.\n",
    "\n",
    "How would you do this when you have more than one hyperparameter? Refer to the book to find the answer to this one (p.318)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Understanding the value of a validation set\n",
    "\n",
    "Following our best practice of splitting the data into training and test sets, we might be\n",
    "tempted to tell people that we have found a model that performs with 97.4% accuracy on\n",
    "the dataset. However, our result might not necessarily generalize to new data. The\n",
    "argument is the same as earlier on in the book when we warranted the train-test split that\n",
    "we need an independent dataset for evaluation.\n",
    "\n",
    "However, when we implemented grid search in the last section, we used the test set to\n",
    "evaluate the outcome of the grid search and update the hyperparameter $k$. This means we\n",
    "can no longer use the test set to evaluate the final data! Any model choices made based on\n",
    "the test set accuracy would leak information from the test set into the model.\n",
    "\n",
    "One way to resolve this data is to split the data again and introduce what is known as a\n",
    "**validation set**. The validation set is different from the training and test set and is used\n",
    "exclusively for selecting the best parameters of the model. It is a good practice to do all\n",
    "exploratory analysis and model selection on this validation set and keep a separate test set,\n",
    "which is only used for the final evaluation.\n",
    "\n",
    "In other words, we should end up splitting the data into three different sets:\n",
    "- a training set, which is used to build the model\n",
    "- a validation set, which is used to select the parameters of the model\n",
    "- a test set, which is used to evaluate the performance of the final model\n",
    "\n",
    "In practice, the three-way split is achieved in two steps.\n",
    "\n",
    "First, split the data into two chunks: one that contains training and validation sets and another\n",
    "that contains the test set:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "X_trainval, X_test, y_trainval, y_test = train_test_split(\n",
    "    X, y, random_state=37\n",
    ")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(112, 4)"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "X_trainval.shape"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Second, split `X_trainval` again into proper training and validation sets:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "X_train, X_valid, y_train, y_valid = train_test_split(\n",
    "    X_trainval, y_trainval, random_state=37\n",
    ")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(84, 4)"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "X_train.shape"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Then we repeat the manual grid search from the preceding code, but this time, we will use\n",
    "the validation set to find the best $k$:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(1.0, 7)"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "best_acc = 0.0\n",
    "best_k = 0\n",
    "for k in range(1, 20):\n",
    "    knn = cv2.ml.KNearest_create()\n",
    "    knn.setDefaultK(k)\n",
    "    knn.train(X_train, cv2.ml.ROW_SAMPLE, y_train)\n",
    "    _, y_valid_hat = knn.predict(X_valid)\n",
    "    acc = accuracy_score(y_valid, y_valid_hat)\n",
    "    if acc >= best_acc:\n",
    "        best_acc = acc\n",
    "        best_k = k\n",
    "best_acc, best_k"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We now find that a 100% validation score (`best_acc`) can be achieved with $k=7$ (`best_k`)!\n",
    "However, recall that this score might be overly optimistic. To find out how well the model\n",
    "really performs, we need to test it on held-out data from the test set.\n",
    "\n",
    "In order to arrive at our final model, we can use the value for $k$ we found during grid search\n",
    "and re-train the model on both the training and validation data. This way, we used as much\n",
    "data as possible to build the model while still honoring the train-test split principle.\n",
    "\n",
    "This means we should retrain the model on `X_trainval`, which contains both the training\n",
    "and validation sets and score it on the test set:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(0.94736842105263153, 7)"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "knn = cv2.ml.KNearest_create()\n",
    "knn.setDefaultK(best_k)\n",
    "knn.train(X_trainval, cv2.ml.ROW_SAMPLE, y_trainval)\n",
    "_, y_test_hat = knn.predict(X_test)\n",
    "accuracy_score(y_test, y_test_hat), best_k"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "With this procedure, we find a formidable score of 94.7% accuracy on the test set. Because\n",
    "we honored the train-test split principle, we can now be sure that this is the performance we\n",
    "can expect from the classifier when applied to novel data. It is not as high as the 100%\n",
    "accuracy reported during validation, but it is still a very good score!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Combining grid search with cross-validation\n",
    "\n",
    "One potential danger of the grid search we just implemented is that the outcome might be\n",
    "relatively sensitive to how exactly we split the data. After all, we might have accidentally\n",
    "chosen a split that put most of the easy-to-classify data points in the test set, resulting in an\n",
    "overly optimistic score. Although we would be happy at first, as soon as we tried the model\n",
    "on some new held-out data, we would find that the actual performance of the classifier is\n",
    "much lower than expected.\n",
    "\n",
    "Instead, we can combine grid search with cross-validation. This way, the data is split\n",
    "multiple times into training and validation sets, and cross-validation is performed at every\n",
    "step of the grid search to evaluate every parameter combination.\n",
    "\n",
    "Because grid search with cross-validation is such a commonly used method for\n",
    "hyperparameter tuning, scikit-learn provides the `GridSearchCV` class, which implements it\n",
    "in the form of an estimator.\n",
    "\n",
    "We can specify all the parameters we want `GridSearchCV` to search over by using a\n",
    "dictionary. Every entry of the dictionary should be of the form `{name: values}`, where\n",
    "`name` is a string that should be equivalent to the parameter name usually passed to the\n",
    "classifier, and `values` is a list of values to try.\n",
    "\n",
    "For example, in order to search for the best value of the parameter `n_neighbors` of the\n",
    "`KNeighborsClassifier` class, we would design the parameter dictionary as follows:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "param_grid = {'n_neighbors': range(1, 20)}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here, we are searching for the best $k$ in the range [1, 19].\n",
    "We then need to pass the parameter grid as well as the classifier (`KNeighborsClassifier`)\n",
    "to the `GridSearchCV` object:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from sklearn.neighbors import KNeighborsClassifier\n",
    "from sklearn.model_selection import GridSearchCV\n",
    "grid_search = GridSearchCV(KNeighborsClassifier(), param_grid, cv=5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Then we can train the classifier using the `fit` method. In return, scikit-learn will inform us\n",
    "about all the parameters used in the grid search:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "GridSearchCV(cv=5, error_score='raise',\n",
       "       estimator=KNeighborsClassifier(algorithm='auto', leaf_size=30, metric='minkowski',\n",
       "           metric_params=None, n_jobs=1, n_neighbors=5, p=2,\n",
       "           weights='uniform'),\n",
       "       fit_params={}, iid=True, n_jobs=1,\n",
       "       param_grid={'n_neighbors': range(1, 20)}, pre_dispatch='2*n_jobs',\n",
       "       refit=True, return_train_score=True, scoring=None, verbose=0)"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "grid_search.fit(X_trainval, y_trainval)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This will allow us to find the best validation score and the corresponding value for $k$:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(0.9642857142857143, {'n_neighbors': 3})"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "grid_search.best_score_, grid_search.best_params_"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We thus get a validation score of 96.4% for $k=3$. Since grid search with cross-validation is\n",
    "more robust than our earlier procedure, we would expect the validation scores to be more\n",
    "realistic than the 100% accuracy we found before.\n",
    "\n",
    "However, from the previous section, we know that this score might still be overly\n",
    "optimistic, so we need to score the classifier on the test set instead:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.97368421052631582"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "grid_search.score(X_test, y_test)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "And to our surprise, the test score is even better."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!--NAVIGATION-->\n",
    "< [Understanding Cross-Validation](11.02-Understanding-Cross-Validation-Bootstrapping-and-McNemar's-Test.ipynb) | [Contents](../README.md) | [Chaining Algorithms Together to Form a Pipeline](11.04-Chaining-Algorithms-Together-to-Form-a-Pipeline.ipynb) >"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.5.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}
